二分搜索树基础

二叉树

image-20190805144343953

特征：

  • 具有唯一的根结点
  • 有左孩子和右孩子
  • 每个节点最多有两个孩子

image-20190805144551652

  • 叶子节点 ：左右孩子为空

    image-20190805144758456

image-20190805144928079

二分搜索树 image-20190805150130621

image-20190805150141302

image-20190805150152680

Tips：存储的元素必须有可比较性

二分搜索树定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//BST 二分搜索树
public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    //根结点
    private Node root;//根结点
    private int size;//记录存储了多少个元素

    public BST() {
        root = null;
        size = 0;
    }
  }

二分搜索树添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//BST 二分搜索树
public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    //根结点
    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //向二分搜索树中添加新的元素
    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else {
            add(root, e);//从根结点开始插入元素e
        }
    }

    //向以node为根的二分搜索树中插入元素E 递归算法
    private void add(Node node, E e) {
        //1  递归终止条件
        if (e.equals(node.e)) {
            return;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        }
        // 2 调用递归函数
        if (e.compareTo(node.e) < 0) {
            add(node.left, e);
        } else
            add(node.right, e);
    }
}

改进二分搜索树 （深入理解终止条件）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//向以node为根的二分搜索树中插入元素E 递归算法
  private Node add(Node node, E e) {
      //1  递归终止条件
      if (node == null) {
          size++;
          return new Node(e);
      }
      // 2 调用递归函数
      if (e.compareTo(node.e) < 0) {
          node.left = add(node.left, e);
      } else if (e.compareTo(node.e) > 0) {
          node.right = add(node.right, e);
      }
      // 实际操作添加的新元素
      return node;

  }

二分搜索树查询元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//看二分搜索树中是否包含元素e
  public boolean contains(E e) {
      return contains(root, e);
  }

  //看以node为根的二分搜索树是否包含元素e 递归算法
  private boolean contains(Node node, E e) {
      if (node == null) {
          return false;
      }
      if (e.compareTo(node.e) == 0) {
          return true;
      } else if (e.compareTo(node.e) < 0) {
          return contains(node.left, e);
      } else   //(e.compareTo(node.e)
          return contains(node.right, e);
  }

二分搜索树前序遍历

image-20190806181212920

1
2
3
4
5
6
7
8
9
10
11
12
//二分搜索树的前序遍历
    public void preOrder() {
        preOrder(root);
    }
    //前序遍历以node为根的二分搜索树 递归算法
    private void proOrder(Node node) {
        if (node == null)
            return;
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

二分搜索树 中序遍历

image-20190806191019980

1
2
3
4
5
6
7
8
9
//中序遍历以node为根的二分搜索树 递归算法
   private void inOrder(Node node) {
       if (node == null) {
           return;
       }
       inOrder(node.left);
       System.out.println(node.e);
       inOrder(node.right);
   }

二分搜索树 后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
//二分搜索树的后序遍历
   private void postOrder() {
       postOrder(root);
   }

   //后序遍历以node为根的二分搜索树 递归算法
   private void postOrder(Node node) {
       if (node == null) return;
       postOrder(node.left);
       postOrder(node.right);
       System.out.println(node.e);
   }

深入理解二分搜索树的遍历

image-20190807083032016

image-20190807083126278

image-20190807083400231

image-20190807083542371

image-20190807083744400

image-20190807084105825

二分搜索树的非递归前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//二分搜索树非递归前序遍历
  public void preOrderNR() {
      Stack<Node> stack = new Stack<>();
      stack.push(root);
      while (!stack.isEmpty()) {
          Node cur = stack.pop();
          System.out.println(cur.e);
          if (cur.right != null) {
              stack.push(cur.right);
          }
          if (cur.left != null) {
              stack.push(cur.left);
          }

      }

二分搜索树的层序遍历

image-20190807085755088

image-20190807090056806

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

TODO 
代码层序遍历

  public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);
            if (cur.left != null)
                q.add(cur.left);
            if (cur.right != null)
                q.add(cur.right);
        }

    }

查找二分搜索树的最小值和最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//寻找二分搜索树的最小元素

 public E minium() {
     if (size == 0)
         throw new IllegalArgumentException("BST size=0");
     return minium(root).e;
 }

 //返回以node为根的二分搜索树的最小值所在的节点
 private Node minum(Node node) {
     if (node.left == null)
         return node;
     return minium(node.left);
 }


//寻找二分搜索树的最小元素

 public E minium() {
     if (size == 0)
         throw new IllegalArgumentException("BST size=0");
     return minium(root).e;
 }

 //返回以node为根的二分搜索树的最小值所在的节点
 private Node minum(Node node) {
     if (node.right == null)
         return node;
     return minium(node.right);
 }

删除二分搜索树的最 大 小值

image-20190810070441031

二分搜索树删除任意节点

image-20190810071009720

image-20190810071121536

image-20190810071241962

image-20190810071308146

image-20190810071318262

在5.2中完成了树的遍历，这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍： 我们要想删除二分搜索树的最小值和最大值，就需要先找到二分搜索树的最小值和最大值，其实也还是很容易的，因为根据二叉搜索树的特点，它的左子树一定比当前节点要小，所以二叉搜索树的最小值一定是左子树一直往下走，一直走到底。同样在二叉搜索树中，右子树节点值，一定比当前节点要大，所以右子树一直往下走，就一定是最大值。

注意向左走一直到走不动并不是一定要达到叶子节点，只用达到走不动为止，看下图的例子:

img

向左走到16就走不动了，但是16下面还有元素。

一、查询操作

1.1 查询二分搜索树的最小节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 寻找二分搜索树的最小元素
   public E minimum() {
       if (size == 0) {
           throw new IllegalArgumentException("BST is empty");
       }

       Node ninNode = minimum(root);
       return ninNode.e;
   }

   // 返回以node为根的二分搜索树的最小值所在的节点
   private Node minimum(Node node) {
       if (node.left == null) {
           return node;
       }

       //返回相应的节点的左子树的最小值
       return minimum(node.left);
   }

1.2 查询二分搜索树的最大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 寻找二分搜索树的最大元素
   public E maxmum() {
       if (size == 0)
           throw new IllegalArgumentException("BST is empty");
       Node maxNode = maxmum(root);

       return maxNode.e;
   }

   // 返回以node为根的二分搜索树的最大值所在的节点
   private Node maxmum(Node node) {
       if (node.right == null) {
           return node;
       }

       return maxmum(node.right);
   }

二、删除操作

删除最小值的思路： 1）如果要删除的节点是叶子节点，那么直接删除 2）如果要删除的节点下面有右子树，那么只用将其下的右子树整体上移成为上一个节点的左子树即可

img

当删除22这个节点后，把33这个节点及其以下的子树变成41节点的左子树即可。

2.1 删除最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public E removeMin() {
      E ret = minimum();//获取最小元素
      root = removeMin(root);

      return ret;
  }

  // 删除掉以node为根的二分搜索树中的最小节点
  // 返回删除节点后新的二分搜索树的根
  private Node removeMin(Node node) {

      // 递归的终止条件，当前节点没有左子树了，那么就是最小节点了
      // 如果是最小节点，我们要做的是删除当前节点，但是当前节点很可能是有右子树的
      // 我们先把该节点的右子树节点保存，然后就删除掉该右子树节点，最后把右子树节点返回即可
      if (node.left == null) {
          Node rightNode = node.right;
          node.right = null; //左节点为空了，让右子树也为空，相当于脱离了树
          size--;
          return rightNode;//返回右子树是为了后面的绑定操作
      }

      // 没有递归到底的情况，那么就递归调用其左子树，这个调用的过程会返回被删除节点的右子树，
      //将返回的右子树重新绑定到上一层的node的左节点上就相当于彻底删除了那个元素
      node.left = removeMin(node.left);

      return node;// 删除后，根节点依然是node，返回即可
  }
2.2 删除最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 从二分搜索树中删除最大值所在节点
   public E removeMax() {
       E ret = maxmum();
       root = removeMax(root);
       return ret;
   }

   // 删除掉以node为根的二分搜索树中的最大节点
   // 返回删除节点后新的二分搜索树的根
   private Node removeMax(Node node) {
       if (node.right == null) {
           Node leftNode = node.left;
           node.left = null;
           size--;
           return leftNode;
       }

       node.right = removeMax(node.right);//等号"="左边的相当于上一次的right,右边相当于下一次返回的结果
       return node;

   }

一.删除思路分析

在删除二叉搜索树的任意元素时，会有三种情况：

1.1 删除只有左孩子的节点

节点删除之后，将左孩子所在的二叉树取代其位置；连在原来节点父亲元素右节点的位置，比如在图中需要删除58这个节点。

img

删除58这个节点后，如下图所示：

img

1.2 删除只有右孩子的节点：

节点删除之后，将右孩子所在的二叉树取代其位置；连在原来节点的位置，比如在下图中需要删除58这个节点。

img

删除58这个节点后，如下图所示：

img

这里需要说明说一下，以上两种情况其实包含了叶子节点情况的，我们可以把叶子节点理解成只有左孩子的节点，也可以把它理解为只有右孩子的节点，只不过左孩子、右孩子为null。

1.3 删除包含左右孩子的节点

如下图，二叉搜索树包含有左右孩子，假设现需要删除58这个节点。

img

针对该种情况，分析如下： 我们把58这个节点记为d节点（包含有左子树与右子树）,如下图所示：

img

针对这种节点删除情况需要把左子树与右子树融合起来，融合方法： 从d这节点的左孩子与右孩子中找一个比d节点还要大的节点取代d节点，根据二叉搜索树的性质可知（左边节点<当前节点<右边节点），这个需要被找的节点存在于d节点的右孩子节点中。

寻找规则： 寻找需要被删除节点58(d)的后继的所有元素中，离 58 最近的且比 58 大的节点，在本例中为59这个节点【即右子树中的最小值】，记为s，如下图所示：

img

删除步骤：

（1）从d的右子树中删除最小值，将删除最小值s后的d的右子树, 变为d后继节点s的右孩子，如下图所示：

img

（2）将d节点（58节点）的左子树，变为后继节点s(59节点)的左子树，如下图所示：

img

(3)将后继节点s（59节点）连接到d节点（58节点）父亲节点的右边，删除d节点（58节点）后,后继s节点（59节点）成为新的根，如下图所示：

img

二、编码实现删除二叉搜索树的任意元素

根据上述的分析，在此基础上进行编码，删除代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//从二叉搜索树中删除元素为e的节点
    public void remove(E e) {
        root = remove(root, e);
    }

    //删除以node为根的二叉搜索树中值为e的节点，递归算法
    //返回删除节点后更新的二叉搜索树的根
    private Node remove(Node node, E e) {
        if (node == null)
            return null;

        if (e.compareTo(node.e) < 0) {//e<node.e (被删除元素e小于当前节点值e)
            node.left = remove(node.left, e);
            return node;
        }
        if (e.compareTo(node.e) > 0) {//e>node.e (被删除元素e大于当前节点值e)
            node.right = remove(node.right, e);
            return node;
        } else {//e==node.e (被删除元素e等于当前节点值e)

            //待删除节点左子树为空情况
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            //待删除节点右子树为空情况
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            //左右子树均不为空
            //方法：找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;

            return successor;
        }
    }

对于上述代码中的minimum函数，在5.3节中已经实现，此处同样也把代码列出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 寻找二分搜索树的最小元素
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }

        Node ninNode = minimum(root);
        return ninNode.e;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        //返回相应的节点的左子树的最小值
        return minimum(node.left);
    }

一.删除思路分析

在删除二叉搜索树的任意元素时，会有三种情况：

1.1 删除只有左孩子的节点

节点删除之后，将左孩子所在的二叉树取代其位置；连在原来节点父亲元素右节点的位置，比如在图中需要删除58这个节点。

img

删除58这个节点后，如下图所示：

img

1.2 删除只有右孩子的节点：

节点删除之后，将右孩子所在的二叉树取代其位置；连在原来节点的位置，比如在下图中需要删除58这个节点。

img

删除58这个节点后，如下图所示：

img

这里需要说明说一下，以上两种情况其实包含了叶子节点情况的，我们可以把叶子节点理解成只有左孩子的节点，也可以把它理解为只有右孩子的节点，只不过左孩子、右孩子为null。

1.3 删除包含左右孩子的节点

如下图，二叉搜索树包含有左右孩子，假设现需要删除58这个节点。

img

针对该种情况，分析如下： 我们把58这个节点记为d节点（包含有左子树与右子树）,如下图所示：

img

针对这种节点删除情况需要把左子树与右子树融合起来，融合方法： 从d这节点的左孩子与右孩子中找一个比d节点还要大的节点取代d节点，根据二叉搜索树的性质可知（左边节点<当前节点<右边节点），这个需要被找的节点存在于d节点的右孩子节点中。

寻找规则： 寻找需要被删除节点58(d)的后继的所有元素中，离 58 最近的且比 58 大的节点，在本例中为59这个节点【即右子树中的最小值】，记为s，如下图所示：

img

删除步骤：

（1）从d的右子树中删除最小值，将删除最小值s后的d的右子树, 变为d后继节点s的右孩子，如下图所示：

img

（2）将d节点（58节点）的左子树，变为后继节点s(59节点)的左子树，如下图所示：

img

(3)将后继节点s（59节点）连接到d节点（58节点）父亲节点的右边，删除d节点（58节点）后,后继s节点（59节点）成为新的根，如下图所示：

img

二、编码实现二叉搜索树的任意元素

根据上述的分析，在此基础上进行编码，删除代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//从二叉搜索树中删除元素为e的节点
    public void remove(E e) {
        root = remove(root, e);
    }

    //删除以node为根的二叉搜索树中值为e的节点，递归算法
    //返回删除节点后更新的二叉搜索树的根
    private Node remove(Node node, E e) {
        if (node == null)
            return null;

        if (e.compareTo(node.e) < 0) {//e<node.e (被删除元素e小于当前节点值e)
            node.left = remove(node.left, e);
            return node;
        }
        if (e.compareTo(node.e) > 0) {//e>node.e (被删除元素e大于当前节点值e)
            node.right = remove(node.right, e);
            return node;
        } else {//e==node.e (被删除元素e等于当前节点值e)

            //待删除节点左子树为空情况
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            //待删除节点右子树为空情况
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            //左右子树均不为空
            //方法：找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;

            return successor;
        }
    }

对于上述代码中的minimum函数，在5.3节中已经实现，此处同样也把代码列出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 寻找二分搜索树的最小元素
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }

        Node ninNode = minimum(root);
        return ninNode.e;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        //返回相应的节点的左子树的最小值
        return minimum(node.left);
    }